# 二叉树的最小深度： https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/submissions/

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def minDepth(self, root: TreeNode) -> int:
        """
            前序遍历，递归。 比较最小值
        """

        if not root: return 0

        minDeepth = 100000
        def inOrder(node, deep):
            nonlocal minDeepth
            if not node: 
                return 

            inOrder(node.left, deep + 1)
            inOrder(node.right, deep + 1)

            # 如果为根节点，计算下当前的深度
            if not node.left and not node.right:
                minDeepth = min(minDeepth, deep)

        inOrder(root, 1)
        return minDeepth

import collections

# 官网的广度优先遍历， 找到叶子节点时，直接返回了，简便
class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root:
            return 0

        que = collections.deque([(root, 1)])
        while que:
            node, depth = que.popleft()
            if not node.left and not node.right:
                return depth
            if node.left:
                que.append((node.left, depth + 1))
            if node.right:
                que.append((node.right, depth + 1))
        
        return 0


